Fonseca trở thành huấn luyện viên ngay sau khi giải nghệ, làm huấn luyện viên đội trẻ Estrela da Amadora trong 2 năm. Từ năm 2007 đến 2011, ông huấn luyện một số đội bóng nhỏ, đáng chú ý là CD Pinhalnovense, ông đã đưa đội đến trận tứ kết Cúp Quốc gia Bồ Đào Nha trong cả hai mùa bóng 2009-10 và 2010-11.[1][2]

Mùa 2011-12, Fonseca được bổ nhiệm làm HLV CD Aves ở giải hai,[3] và ông đã dẫn dắt đội đến vị trí thứ 3 chung cuộc, thiếu 2 điểm để lên hạng. Trong mùa giải tiếp theo, ông trở thành HLV của FC Paços de Ferreira, một lần nữa kết thúc mùa giải ở vị trí thứ ba, đủ điều kiện tham dự vòng sơ loại tại UEFA Champions League; nổi bật trong mùa giải đó bao gồm chiến thắng cả hai trận đấu với Braga (2-0 trên sân nhà, 3-2 trên sân khách) và Sporting CP (1-0 trong cả lần đối đầu).[4][5]

Ngày 10 tháng 6 năm 2013, Fonseca kế nhiệm Vítor Pereira làm huấn luyện viên trưởng của nhà đương kim vô địch quốc gia FC Porto, với bản hợp đồng 2 năm.[6][7] Ông bắt đầu tạo sự chú ý bằng chiến thắng tại siêu cúp Bồ Đào Nha sau chiến thắng 3-0 trước Vitória de Guimarães, giành được danh hiệu đầu tiên của mình trên cương vị huấn luyện viên.[8][9]

Tuy nhiên, vào ngày 05 tháng 3 năm 2014, sau chuỗi kết quả tồi tệ khiến câu lạc bộ rơi khỏi vị trí thứ 3, kém 9 điểm so với các đội đầu bảng SL Benfica, Fonseca đã bị sa thải.[10] Trước đó, vào ngày 12 tháng 01, ông đã tuyên bố rằng Porto sẽ trở thành nhà vô địch trong trận đấu cuối cùng trước chính đối thủ.[11]

Từ 2014 đến 2016, Fonseca tiếp tục là huấn luyện viên của Paços [12] và SC Braga.[13] Ông dẫn dắt SC Braga đến vị trí thứ 4 giải VĐQG, và giành cúp quốc gia.[14]

Ngày 31 tháng 5 năm 2016, Fonseca lần đầu tiên chuyển ra nước ngoài trong sự nghiệp, làm HLV của Shakhtar Donetsk thế huyền thoại Mircea Lucescu (HLV của đội 12 mùa trước đó), ký hợp đồng 2 năm với đội bóng thi đấu ở giải Premier League Ukraine.[15][16] Ông đã giành chức vô địch quốc gia trong cả ba mùa, hơn nữa cũng giành được cú đúp trong cả ba mùa - điều đó giúp ông trở thành huấn luyện viên xuất sắc nhất giải đấu [17]. Ông giúp đội lọt vào vòng 16 đội UEFA Champions League 2017-18 [18] khi kết thúc vòng bảng ở vị trí thứ hai, sau chiến thắng 2-1 trên sân nhà trước đội bóng đang thi đấu ở Premier League, Manchester City [19]

Vào ngày 11 tháng 6 năm 2019, Fonseca được bổ nhiệm làm HLV của AS Roma.[20]